iT邦幫忙

2021 iThome 鐵人賽

DAY 9
0

Leetcode #2. Add Two Numbers

簡單來說就是要做兩個鏈結的加總

ex.1
Input: list 1: 2->4->3, list 2: 5->6->4
Output: [7,0,8]
342 + 465 = 807 (個位數在鏈結的最左邊)

如果你沒做過這題,強烈建議你先思考一下怎麼解。


防雷
防雷
防雷


這一題主要讓你熟悉鏈結的操作,只要搞懂了鏈結,花點時間就可以寫出來。
只要每一次加總,處理一下進位,應該就可以解決了,時間複雜度為O(n)

程式:

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	node := &ListNode{}
	temp := node
	curry := 0 // 記錄有沒有進位

	for {
        // 兩個鏈結長度可能不一樣,只要一邊有東西,還是要加總下去
		if l1 == nil && l2 == nil {
			break
		}

		num := 0
		if l1 != nil {
			num += l1.Val
			l1 = l1.Next
		}

		if l2 != nil {
			num += l2.Val
			l2 = l2.Next
		}

        // 判斷進位
		num += curry
		if num >= 10 {
			num = num % 10
			curry = 1
		} else {
			curry = 0
		}

		temp.Next = &ListNode{
			Val: num,
		}
		temp = temp.Next
	}

	if curry == 1 {
		temp.Next = &ListNode{
			Val: 1,
		}
	}

	return node.Next
}

明天來講Queue & Stack!


上一篇
Day.8 Reverse Linked List
下一篇
Day.10 Stack
系列文
算法30天30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言